package primary.linkedList;



/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class MergeTwoLists {
    /*
        123 134 合并为 112334 采用尾插法
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        ListNode fakeHead = new ListNode(0,null);
        ListNode tail = fakeHead;
        ListNode temp;
        while(list1 != null && list2 != null){
            // 找到插入节点
            if(list1.val < list2.val){
                temp = list1;
                list1 = list1.next;
            }else{
                temp = list2;
                list2 = list2.next;
            }
            // 将temp插入新的头中
            tail.next = temp;
            tail = temp;
        }
        while(list1 != null){
            temp = list1;
            list1 = list1.next;
            tail.next = temp;
            tail = temp;
        }
        while(list2 != null){
            temp = list2;
            list2 = list2.next;
            tail.next = temp;
            tail = temp;
        }
        // 处理尾节点
        tail.next = null;
        return fakeHead.next;
    }
}
